home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1996 #15 / Monster Media Number 15 (Monster Media)(July 1996).ISO / math / hugemath.zip / HUGEMATH.DOC < prev    next >
Text File  |  1996-04-06  |  11KB  |  262 lines
  1. /*
  2.    HUGEMATH DOCUMENT EXPLAINING BASIC USAGE
  3.    This program is basically a calculator which works with integers
  4.    These can be more or less as large as you want. The exe file supplied
  5.    has been compiled to accept integers up to about 500 digits each.
  6.    Some of the code may be difficult to read because it has been optimised
  7.    as far as possible. Many primality tests have also been implemented.
  8.    See the doc file for a description of usage.
  9.  
  10.    This program was written by Paul Young, using Turbo C++.
  11.    I accept no responsibility for use or misuse of this program in any way.
  12.    This program is Public Domain.
  13.    It may be copied freely provided this notice is included.
  14.    This program may be used as a base or included in other programs
  15.    however these programs must also be Public Domain and no monetary gain
  16.    should be made from these. Help support Public Domain programming.
  17.    E-Mail P Young, 101716.3323@compuserve.com
  18. */
  19.    
  20. REGISTERS
  21. ---------
  22. NB This program should be easily extendible using a C Compiler with the
  23. routines already present.
  24.  
  25. You have four registers available for calculations - a,b,c and d.
  26. Commands are entered directly to the program in the form of
  27. command reg1,reg2/number
  28. For example :
  29. equ a,100              ;sets register a to 100.
  30. add a,b                ;adds register b to register a.
  31. Some commands only have one argument for example
  32. pri a                  ;prints register a to screen.
  33. mul2 a                 ;a fast multiply of a by 2.
  34. or no arguments for example
  35. priall                 ;prints all register values to screen
  36.  
  37. The power of the program is its ability to handle very large numbers and
  38. it has some powerful factorisation abilities.
  39.  
  40. COMMANDS
  41. --------
  42. All commands will be presented in the following way :
  43. add reg1,reg2|num        
  44. means that the command 'add' takes the two arguments reg1 (for example 'a')               
  45. and reg2 (for example 'b') or a number instead of reg2 (for example 123456).
  46. So valid commands are :
  47. add d,c
  48. add a,b
  49. add a,124563554987698
  50. Where further explanation is necessary this will follow later.
  51.  
  52. COMMAND SUMMARY               
  53. ---------------
  54. Command                        Action
  55. --------------------------------------
  56. add reg1,reg2|num             ;reg1=reg1+reg2|num
  57. div reg1,reg2|num             ;reg1=reg1/reg2|num
  58. mul reg1,reg2|num             ;reg1=reg1*reg2|num
  59. sub reg1,reg2|num             ;reg1=reg1-reg2|num
  60. mod reg1,reg2|num             ;reg1=reg1 mod reg2|num
  61. priall                        ;prints all regs to screen
  62. pri reg1                      ;prints value of reg1 to screen
  63. inc reg1                      ;reg1=reg1+1
  64. dec reg1                      ;reg1=reg1-1
  65. equ reg1,reg2|num             ;reg1=reg2|num
  66. swap reg1,reg2                ;swaps values of reg1 and reg2
  67. mul2 reg1                     ;reg1=reg1*2 (faster than mul)
  68. div2 reg1                     ;reg1=reg1/2 (faster than div)
  69. rep reg1,num                  ;reg1=num'th repunit
  70. fib reg1,num                  ;reg1=num'th fibonacci number
  71. smallfac reg1                 ;removes small factors(<65536) of reg1
  72. mer reg1,num                  ;reg1=num'th mersenne number
  73. tdiv reg1,num                 ;trial divides reg1 by k*num+-1
  74. gcd reg1,reg2|num             ;reg1=gcd(reg1,reg2)
  75. mprime reg1,num               ;reg1=3*5*7*11*... for primes<num
  76. root reg1,reg2|num            ;reg1=squareroot(reg2|num)
  77. psp reg1,num                  ;tests reg1 for num-pseudoprime
  78. pollard reg1,num              ;pollards factorisation
  79. autopsp reg1,num              ;tests reg1 for k-pseudoprime,k<num
  80. monte reg1,num                ;montecarlo factorisation
  81. sequence reg1,num             ;sequence factorisation
  82. findwitness reg1,reg2|num     ;used in prime testing
  83. proveprime reg1,reg2          ;prime test
  84. 2pow reg1,num                 ;reg1=2^num (fast)
  85. npow reg1,num                 ;reg1=reg1^num
  86. factorial reg1,num            ;reg1=num!
  87. fermat reg1                   ;fermats method of factorisation
  88. quit                          ;quit the program
  89.  
  90. ADDITIONAL NOTES
  91. ----------------
  92. When factorising large numbers ALWAYS use smallfac first. This will find
  93. small factors very quickly and some methods assume small factors have been
  94. removed. Other methods also run quicker the smaller the numbers present.
  95. The next thing to do is really a psp test. This will not prove primality 
  96. but will show whether a number may be prime or is definitely composite. It
  97. is also quite quick.
  98. If a number is definitely composite then there are a number of choices open.
  99. Remember that no program is a substitute for a good background knowledge of
  100. number theory and with preparatory work a factorisation can usually be found
  101. quicker.
  102. With most of the methods below pressing a key will give some idea of how far
  103. calculations have gone and pressing 'e' will stop it.
  104. Tdiv
  105. ----
  106. This is trial division. If nothing is known of the number then use tdiv a,6 
  107. assuming the number is in register 'a'. If factors are known to be of the 
  108. form 1024k+-1 say then use tdiv a,1024.
  109. Pollard
  110. -------
  111. This can be a useful method and uses similar calculations to a psp test. It
  112. will find a factor n quickly where n-1 has an 'easy' factorisation. The num
  113. argument is the base, as for psp tests. Try first with 2 or 3 and if one of 
  114. these throws you out (doesn't happen very often but will with mersenne 
  115. numbers and a base of 2 then try another. Don't wait too long, if a factor
  116. isn't found in a reasonable amount of time then you could have a long wait.
  117. Fermat
  118. ------
  119. This is a classic method found in most texts. It works best when both factors
  120. are roughly the same size. Keypresses will take some time to register. I have
  121. tried to speed the method up as far as possible with a 20-value sieve but 
  122. it's still not that good on large numbers.
  123. Sequence
  124. --------
  125. Also known as Pollards rho method. Again a starting value is used. I've had
  126. some good results with this one. Be patient. It works by looking for repeated
  127. values in a sequence which will hopefully be fairly short with respect to one
  128. of the factors. Best left rather than restarting with a new value. There is
  129. room for optimisation here - see H Riesels 'Computer Methods of 
  130. Factorisation.' , Springer Verlag.
  131. Monte Carlo
  132. -----------
  133. I leave it to you to try this but I've found it to be crap. Needs a decent
  134. algorithm but I couldn't find any dissimilar to sequence which is better.
  135.  
  136. Proof Of Primality
  137. ------------------
  138. I have implemented the n-1 method of proving primality as far as possible.
  139. This is the proveprime command. The reg2 argument will be used to store any
  140. residue. Normally this can prove a number to prime by factoring n-1 and 
  141. performing tests similar to psp tests. The problem comes when n-1 can't be
  142. fully factored in a short space of time. Instead of leaving the program to
  143. go off and do it's own thing I decided to dump the remainder of n-1 (the
  144. unfactored part) in reg2 and leave it to the user. What you now have to do
  145. is factor reg2 in some way and then use findwitness (witness is a bad name
  146. here as it really means something else) to make the tests.
  147.  
  148. Most of the other commands should be straightforward so lets look at an
  149. example now.
  150.  
  151. EXAMPLES
  152. --------
  153. What follows are two sessions using some of the above tests. User input
  154. follows the Command> prompt. I have put comments in beginning with //.
  155. Example 1
  156. ---------
  157. // We will factorise the 89th Fibonacci number.
  158. Command> fib a,89
  159. Command> pri a
  160. 1779979416004714189
  161. Command> smallfac a
  162. Factor : 1069
  163. Command> pri a
  164. 1665088321800481
  165. Command> psp a,2
  166. Pseudoprime
  167. // Knowing this is a 2-pseudoprime we will try to prove primality
  168. Command> proveprime a,b
  169. .
  170. .
  171. . // We receive a lot of information about factors of a-1
  172. . // and pseudoprimes. If the number is found to be composite
  173. . // at any point then the test will end with a message to this effect.
  174. .
  175. N is prime
  176. Command>  // We have now completed this factorisation
  177. // The final result is f(89) = 1069 * 1665088321800481
  178.  
  179. Example 2
  180. ---------
  181. // This will be a more complicated example.
  182. // This time we will factorise the 205th Fibonacci number.
  183. Command> fib a,205
  184. Command> pri a
  185. 3111581989804070186099320645726169127737705
  186. Command> smallfac a
  187. Factor : 5
  188. Factor : 821
  189. Factor : 2789
  190. Factor : 59369
  191. Command> pri a
  192. 4577831883071909637186705446981
  193. Command> psp a,2
  194. Composite
  195. // We will have to search for a factor using one of the above methods
  196. Command> pollard a,2        // purely arbitrary
  197. Factor : 125598581          // found very quickly
  198. // We will need to check that this is prime also since this is a general
  199. // method of factorisation and only splits the number into two factors.
  200. Command> equ c,125598581
  201. Command> psp c,2
  202. Pseudoprime
  203. Command> proveprime c,d
  204. .
  205. .  // loads of info again
  206. .
  207. .
  208. N is prime   // ok , we have another prime factor of f(205)
  209. Command> pri a
  210. 36448117857891321536401     // this is what we have left
  211. Command> psp a,2
  212. Pseudoprime
  213. Command> proveprime a,b
  214. .
  215. .  // loads of info again
  216. .
  217. .
  218. Test unfinished - residue left to be checked    // oh dear
  219. Command> pri b
  220. 740815403615677267      // this is the residue
  221. // we need to factorise it and test each factor with the original 'a'
  222. // using findwitness to complete the test.
  223. Command> psp b,2
  224. Composite
  225. Command> pollard b,2
  226. Factor : 110991193     // this took about 1 minute on a DX2
  227. // Since this is only about 10000*10000 and we know that it has no
  228. // factors less than 65536 since the original test couldn't factorise
  229. // it, it must be prime. So theres no need to check but you can if you
  230. // want to.
  231. Command> findwitness a,110991193
  232. witness 2 - checking pseudoprime
  233. Pseudoprime
  234. // This means we're in the clear. A witness was found and proved to be
  235. // valid. If no witness is found (unlikely) the test fails and you will
  236. // have to find some other way. The last line tells us this was ok. If
  237. // this had said Composite then the original number would be composite.
  238. Command> pri b
  239. 6674542219
  240. // this is whats left from the unfinished test.
  241. Command> proveprime b,2   // we'll try to show it's prime and finish it off
  242. .
  243. .  // loads more info
  244. .
  245. .
  246. N is prime   // good
  247. Command> findwitness a,b    // going for the kill
  248. witness 2 - checking pseudoprime
  249. Pseudoprime
  250. // well that's it all done.
  251. // lets put that result together :
  252. // f(205) = 5 * 821 * 2789 * 59369 * 125598581 * 36448117857891321536401
  253. // and thats all there is to it.
  254. // Happy prime hunting.
  255.  
  256. REQUEST
  257. -------
  258. Does anyone have details on the algorithm used in elliptic curve 
  259. factorisation ? or MPQS ? I would like a copy.
  260. Please send to :
  261. P Young, 101716.3323@compuserve.com
  262.